package Partition;

import java.util.Arrays;
import java.util.Random;
/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-02-19
 * Time:15:48
 * Text：最小的k个数，重点在于k个数是否小于左半部分，或者小于左+中部分
 */
public class Text4 {
    public static void swap(int[] arr,int left,int right){
        int num=arr[left];
        arr[left]=arr[right];
        arr[right]=num;
    }
    public static void qsort(int[] arr,int l,int r,int k){
        if(l>r){
            return;
        }
        int key=arr[new Random().nextInt(r-l+1)+l];
        int left = l-1,right=r+1,i=l;
        while(i<right){
            if(arr[i]<key) swap(arr,++left,i++);
            else if(arr[i]>key) swap(arr,--right,i);
            else i++;
        }
        int a=left-l+1,b=right-left-1;
        if(a>k){
            qsort(arr,l,left,k);
        }else if(a+b>=k){
            return;
        }else{
            qsort(arr,right,r,k-a-b);
        }


    }
    public static int[] smallestK(int[] arr, int k) {
        qsort(arr,0,arr.length-1,k);
        return Arrays.copyOf(arr,k);
    }

    public static void main(String[] args) {
        int[] arr={1,3,5,2,7,4,3,5,1};
        smallestK(arr,3);
    }
}
